package com.company.algo.DP.palindromic;

/**647. 回文子串
 给定一个字符串，计算这个字符串中有多少个回文子串。
 es: 输入："abc" 输出：3 解释：三个回文子串: "a", "b", "c"
 dp[i][j]：s[i:j]【是否是回文子串】
 dp[i][j] =
    1. s[i]!=s[j],则dp[i][j]=false;
    2. s[i]==s[j],则有三种情况
        2.1 当i==j，即单个字符记为回文子串，dp[i][j]=true
        2.2 当|i-j|==1,如"aa"，为回文子串，dp[i][j] = true
        2.3 其他情况：dp[i][j] = dp[i+1][j-1]
 总结dp[i][j] <- dp[i+1][j-1]，所以遍历的顺序对应i应为逆序，j应为正序
 初始化dp[i][j]=false;
 【对应有双指针法是逻辑更情绪且复杂度更优的解法】-掌握
 */
public class CountPalindromicSubstring {
    public int countSubstrings1(String s) {
        boolean[][]dp = new boolean[s.length()][s.length()];
        int count = 0;
        for (int i = s.length()-1; i >= 0 ; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i)==s.charAt(j) && (j-i <= 1 || dp[i+1][j-1])){
                    count++;
                    dp[i][j] = true;
                }
            }
        }
        return count;
    }

    /*双指针法
    ⾸先确定回⽂串，就是找中⼼然后想两边扩散看是不是对称的就可以了
    在遍历中⼼点的时候，要注意中⼼点有两种情况
    ⼀个元素可以作为中⼼点，两个元素也可以作为中⼼点
    */
    public int countSubstrings(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            res += extend(s,i,i,s.length());    //以i为中心向外扩散
            res += extend(s,i,i+1,s.length());  //以i和i+1为中心向外扩散
        }
        return res;
    }

    private int extend(String s, int i, int j, int n) {
        int res = 0;
        while (i>=0 && j<n && s.charAt(i)==s.charAt(j)){
            i--;
            j++;
            res++;
        }
        return res;
    }
}
